package greedy;

/**
 * @author pengfei.hpf
 * @date 2020/3/6
 * @verdion 1.0.0
 * 给定一个正整数 a，找出最小的正整数 b 使得 b 的所有数位相乘恰好等于 a。
 *
 * 如果不存在这样的结果或者结果不是 32 位有符号整数，返回 0。
 *
 *  
 *
 * 样例 1
 *
 * 输入：
 *
 * 48
 * 输出：
 *
 * 68
 *  
 *
 * 样例 2
 *
 * 输入：
 *
 * 15
 * 输出：
 *
 * 35
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-factorization
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SmallestFactorization {
    public int smallestFactorization(int a) {
        if(a < 2){
            return a;
        }
        long mul = 1;
        long res = 0;
        for(int i = 9; i >= 2; i--){
            while(a %i == 0){
                a = a/i;
                res += i*mul;
                mul *= 10;
            }
        }
        return a < 2 && res <= Integer.MAX_VALUE? (int)res :0;
    }
}
